package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/9/6 22:49
 * @description
 */
public class T46全排列 {
    int len =0;
    List<List<Integer>> result  = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        len =nums.length;
        dfs(new ArrayList<>(),0,nums,new boolean[len]);
        return result;
    }

    private void dfs(List<Integer> list,int depth,int[] nums,boolean[] used){
        if (depth==len){
            result.add(new ArrayList<>(list));
        }
        for (int i =0;i<len;i++){
            if (!used[i]){
                used[i]=true;
                list.add(nums[i]);
                dfs(list,depth+1,nums,used);
                //回溯的过程
                used[i]=false;
                list.remove(list.size()-1);
            }
        }
    }
}
